/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: syyyy
 * Date: 2025-11-15
 * Time: 10:04
 */
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class NQueens {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>(); // 存储所有解
        char[][] board = new char[n][n]; // 棋盘：'.'表示空，'Q'表示皇后
        // 初始化棋盘为全'.'
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }
        backtrack(result, board, 0, n); // 从第0行开始回溯
        return result;
    }

    // 回溯函数：在第row行放置皇后
    private void backtrack(List<List<String>> result, char[][] board, int row, int n) {
        // 终止条件：所有行都放好了皇后（找到一个解）
        if (row == n) {
            result.add(convertBoardToList(board)); // 转换棋盘为字符串列表，加入结果
            return;
        }

        // 尝试在当前行的每一列放置皇后
        for (int col = 0; col < n; col++) {
            // 检查当前位置(row, col)是否可以放皇后
            if (isValid(board, row, col, n)) {
                board[row][col] = 'Q'; // 放置皇后
                backtrack(result, board, row + 1, n); // 递归处理下一行
                board[row][col] = '.'; // 回溯：撤销当前放置（尝试其他列）
            }
        }
    }

    // 检查(row, col)位置是否可以放皇后（无冲突）
    private boolean isValid(char[][] board, int row, int col, int n) {
        // 1. 检查当前列是否已有皇后（同一列）
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }

        // 2. 检查左上→右下对角线（行-列 差相等）
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        // 3. 检查右上→左下对角线（行+列 和相等）
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        return true; // 无冲突，可放置
    }

    // 将char[][]棋盘转换为List<String>（方便结果存储）
    private List<String> convertBoardToList(char[][] board) {
        List<String> list = new ArrayList<>();
        for (char[] row : board) {
            list.add(new String(row));
        }
        return list;
    }

    // 测试
    public static void main(String[] args) {
        NQueens solution = new NQueens();
        List<List<String>> solutions = solution.solveNQueens(4); // 求解4皇后问题
        // 打印所有解
        for (List<String> sol : solutions) {
            System.out.println("解法：");
            for (String row : sol) {
                System.out.println(row);
            }
            System.out.println();
        }
    }
}
